import static javafx.scene.input.KeyCode.K;
import static javafx.scene.input.KeyCode.V;

/**
 * Created with IntelliJ IDEA.
 * Description:泛型哈希桶
 * User: lenovo
 * Date: 2023-02-24
 * Time: 8:35
 */
public class GenericityHashBuck<V, K> {
    //f泛型节点
    static class Node<K,V>{
        K key;
        V val;
        Node<K,V> next;
        //构造方法
        public Node(K key,V val){
            this.key =key;
            this.val = val;

        }
    }
    //泛型数组:java里是不能直接new泛型数组的:Node<K,V> [] array = new Node<K,V>[10];
    private Node<K,V> [] array = (Node<K,V>[])new Node[10];
    //哈希桶的计数器
    private int usedSize;
    //负载因子
    private static final float DEFAULT_LOAD_FACTOR = 0.75F;

    public void put(K key,V val){
        //1.new出节点
        Node<K,V> node = new Node<>(key,val);
        //2.根据key计算哈希值:引用类型得调用object类的hashcode将地址转为哈希值
        int hash = key.hashCode();
        int index =hash %array.length;
        //3.从index处的表头开始遍历
        Node<K,V> cur = array[index];
        while(cur!=null){
            //找到了相同的key,更新对应value
            if(cur.key.equals(key)){
                cur.val = val;
                return;
            }
            cur =cur.next;
        }
        //while循环走完,没有找到相同的key,头插
        node.next= array[index];
        array[index] = node;
        //计数器+1
        usedSize++;
        //判断负载因子
        if(loadFactor()>=DEFAULT_LOAD_FACTOR){
            grow();
        }

    }

    public void put2(K key,V val) {
        Node<K,V> node = new Node<>(key,val);
        int hash = key.hashCode();
        int index = hash % array.length;

        Node<K,V> cur = array[index];
        while (cur != null) {
            if(cur.key.equals(key)) {
                cur.val = val;
            }
            cur = cur.next;
        }

        node.next = array[index];
        array[index] = node;
        usedSize++;

        this.usedSize++;
        //扩容自己完善
    }
    //扩容:2倍扩容
    private void grow() {
        //1.构造出新的数组:Node类型的数组转为泛型数组
        Node<K,V>[] newArray = (Node<K, V> []) new Node[array.length*2];
        /**
         * 1.遍历旧的数组,将原先的节点重新哈希:注意是针对每个节点都进行重新hash(cur指向的节点),因此hash函数要写在遍历链表的循环里
         * 2.int index=key%newArray.length
         * 3.将原先的节点头插进新的数组里
         */
        for (int i = 0; i < array.length; i++) {
            if(array[i] != null){
                //从表头开始遍历链表的上的每个节点并进行头插
                Node<K,V> cur = array[i];
                while(cur != null){
                    //由于是将节点插入到了新的数组里,所以会改变节点cur的next,从而将原数组里cur后面的节点都丢掉
                    //所以需要一个curNext来记录cur后面的节点
                    Node<K,V> curNext = cur.next;
                    //重新哈希:对cur指向的节点进行重新hash
                    int index = cur.key.hashCode()%newArray.length;
                    //开始头插
                    cur.next =newArray[index];
                    newArray[index] = cur;
                    cur=curNext;
                }
            }

        }
        //.
        this.array = newArray;

    }

    public V get(K key){
        //1.哈希找到数组里链表的位置
        int hash =key.hashCode();
        int index = hash%array.length;
        //2.从index处的头结点进行遍历
        Node<K,V> cur = array[index];
        while(cur!=null){
            //找到了返回key对应的value
            if (cur.key.equals(key)) {
                return cur.val;
            }
            cur=cur.next;
        }
        //循环走完没有找到
        return null;
    }
    private float loadFactor() {
        return this.usedSize*1.0f/array.length;
    }


}
